import { BinarySearchTree, Node } from "./Tree";
import { Compare, defaultCompare } from "./utils";

export enum Colors {
    RED = 0,
    BLACK = 1
}

export class RedBlackNode<K> extends Node<K>{
    left: RedBlackNode<K>;
    right: RedBlackNode<K>;
    parent: RedBlackNode<K>;
    color: Colors;

    constructor(public key: K) {
        super(key);
        this.color = Colors.RED;
    }

    isRed() {
        return this.color === Colors.RED;
    }

    flipColor() {
        if (this.color === Colors.RED) {
            this.color = Colors.BLACK;
        } else {
            this.color = Colors.RED;
        }
    }
}


export class RedBlackTree<T> extends BinarySearchTree<T> {
    protected root: RedBlackNode<T>;

    insert(key: T) {
        if (this.root == null) {
            this.root = new RedBlackNode(key);
            this.root.color = Colors.BLACK;
        } else {
            let newNode = this.insertNode(this.root, key);
            this.fixTreeProperties(newNode);
        }
    }

    protected insertNode(node: RedBlackNode<T>, key: T): RedBlackNode<T> {
        if (defaultCompare(key, node.key) === Compare.LESS_THAN) {
            if (node.left == null) {
                node.left = new RedBlackNode(key);
                node.left.parent = node;
                return node.left;
            } else {
                return this.insertNode(node.left, key);
            }
        } else if (node.right == null) {
            node.right = new RedBlackNode(key);
            node.right.parent = node;
            return node.right;
        } else {
            return this.insertNode(node.right, key);
        }
    }

    private fixTreeProperties(node: RedBlackNode<T>) {
        while (node && node.parent && node.parent.color == Colors.RED && node.color !== Colors.BLACK) {
            let parent = node.parent;
            const grandParent = parent.parent;
            if (grandParent && grandParent.left === parent) {
                const uncle = grandParent.right;
                if (uncle && uncle.color == Colors.RED) {
                    grandParent.color = Colors.RED;
                    parent.color = Colors.BLACK;
                    uncle.color = Colors.BLACK;
                    node = grandParent;
                } else {
                    if (node == parent.right) {
                        this.rota
                    }
                }
            }
        }
    }


    /**
    * Left left case: rotate right
    *       b                           a
    *      / \                         / \
    *     a   e -> rotationLL(b) ->   c   b
    *    / \                             / \
    *   c   d                           d   e
    */
    private rotationLL(node: RedBlackNode<T>) {
        const temp = node.left;
        node.left = temp.right;
        if (temp.right && temp.right.key) {
            temp.right.parent = node;
        }
        temp.parent = node.parent;
        if (!node.parent) {
            this.root = temp;
        } else {
            if (node === node.parent.left) {
                node.parent.left = temp;
            } else {
                node.parent.right = temp;
            }
        }
        temp.right = node;
        node.parent = temp; 
    }

}